#ifndef L4_D202409_H
#define L4_D202409_H
#include <iostream>
using namespace std;

const int MOD = 1000000007;

/** Q1 有几个 PAT
 *
 * 输入：一个字符串，只包含 P、A、T 三个字符
 *
 * 输出：一个整数，表示字符串中有多少个 PAT 子串
 *
 * 解题思路：
 * 1. 创建两个数组 leftP[i] 表示以 i 结尾的 P 的个数，rightT[i] 表示以 i 开头的
 * T 的个数
 * 2. 遍历字符串，找到每个 A 的位置 i，该位置 A 组成的 PAT 子串数 n[k] =
 * leftP[i] * rightT[i]
 * 3. 累加 n[k] 得到结果
 */
void Q1() {
  string s;
  cin >> s;
  int l = s.size(), ans = 0;
  // 状态转移方程
  // leftP[i] 表示 i 处的 P 的个数
  // s[i] == 'P' leftP[i] = leftP[i-1] + 1
  // s[i] != 'P' leftP[i] = leftP[i-1]
  // 暴力算法时间复杂度 O(n^3)
  // 动态规划时间复杂度 O(2n)
  // leftP i 处左边 P 的个数，rightT i 处右边 T 的个数
  int leftP[l] = {0}, rightT[l] = {0};
  leftP[0] = (s[0] == 'P') ? 1 : 0;           // 初始化最左边
  rightT[l - 1] = (s[l - 1] == 'T') ? 1 : 0;  // 初始化最右边
  for (int i = 1; i < l; i++) {
    leftP[i] = (s[i] == 'P') ? leftP[i - 1] + 1 : leftP[i - 1];
    rightT[l - 1 - i] =
        (s[l - 1 - i] == 'T') ? rightT[l - i] + 1 : rightT[l - i];
  }
  for (int i = 1; i < l; i++) {
    if (s[i] == 'A') {
      ans += leftP[i] * rightT[i];  // i 处 PAT 数量 = 左边 P 数量 * 右边 T 数量
    }
  }
  cout << ans << endl;
}
/** Q2 彩带
 *
 * 输入：
 * 1. n 颜色一共的种类数量，
 * 2. m 织女喜欢的颜色种类数量，like[m] 织女喜欢的顺序
 * 3. l 原始彩带长度，origin[l] 原始彩带
 *
 * 输出：按织女喜欢的颜色顺序裁剪重缝后能达到的最大长度
 *
 * 解题思路：
 *
 */
void Q2() {
  // 接收输入
  int n, m, l;
  cin >> n >> m;
  int like[m];
  for (int i = 0; i < m; i++) {
    cin >> like[i];
  }
  cin >> l;
  int origin[l];
  for (int i = 0; i < l; i++) {
    cin >> origin[i];
  }
  // 输出结果
}

/** Q3 最长峰形线
 *
 * 输入：n -> [3,10^4]; a[i]: [-1000,1000]
 *
 * 输出：长度、峰顶序号（从 1 开始）、峰值
 *
 * 解题思路：
 *
 */
void Q3() {
  // 输入
  int n, i = 1, j = 0, max = 0, top;
  cin >> n;
  int a[n], sf[(--n - 2) / 2] = {0};
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  // 找山峰
  while (i < n - 1) {
    if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
      sf[j] = i + 1;
      j++;
    }
    i++;
  }
  i = 0;
  while (sf[i] != 0) {
    int l = sf[i] - 2;
    int r = sf[i];
    while (a[l] > a[l - 1] && l >= 0) {
      l--;
    }
    while (a[r] > a[r + 1] && r < n) {
      r++;
    }
    int len = r - l + 1;
    if (len > max) {
      max = len;
      top = sf[i];
    }
    i++;
  }
  // 输出
  cout << max << ' ' << top << ' ' << a[top - 1] << endl;
}

/** Q4 红蓝串
 *
 * 输入：n 结果串珠子数，a 红珠子数，b 蓝珠子数
 *
 * 输出：有多少种不同的穿法
 *
 * 解题思路：递归
 *
 */

// n 颗珠子
// a 个红珠子
// b 个蓝珠子
// i 第几步
long long resolve4(int n, int a, int b, int i) {
  long long count = 0;
  if (n > i) {
    if (a >= i) {
      count += resolve4(n - i, a - i, b, i + 1);
    }
    if (b >= i) {
      count += resolve4(n - i, a, b - i, i + 1);
    }
    return count;
  } else {
    if (a >= n)
      count++;
    if (b >= n)
      count++;
    return count;
  }
}

void Q4() {
  int n, a, b;
  cin >> n >> a >> b;
  // 1 + 2 + ... + k = n
  cout << resolve4(n, a, b, 1) % MOD << endl;
}

#endif